#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define NAMESIZE 20                 // 名称允许长度
#define TRUE 1
#define FALSE 0
#define STATUS int
#define EqualFun strcmp
#define SetValue strcpy
typedef char NODE[NAMESIZE];        // 节点名称类型
struct NEIGHBORNODE				
{//节点类型
    NODE node;					// 节点
    struct NEIGHBORNODE *next;	// 邻近节点
};
typedef struct NEIGHBORNODE *NEIGHBOR; // 相邻节点类型
struct ANODE				
{// 节点类型
    NODE node;					// 节点
    NEIGHBOR adjacents;			//邻近节点 
};
typedef struct ANODE ANYNODE;	//节点类型
struct GRAPHNODE				
{//图的节点存储类型 
    ANYNODE node;               // 节点
    struct GRAPHNODE *next;     // 其他节点
};
typedef struct NEIGHBORNODE *PATH;				//路径类型
struct Paths        
{  // 路径集合类型
    PATH path;                                  // 一条路径
    struct Paths *next;                         // 下一条路径
};
typedef struct Paths *PATHS;                    // 路径集合类型
typedef struct GRAPHNODE *GRAPH;                // 图类型


int Equal(NODE n1, NODE n2, int (*fun)()) 
{
    return (int)fun(n1, n2);
}

void Set(NODE n1, NODE n2, char *(fun)())
{
    fun(n1, n2);
}

NEIGHBOR AddANeighbor(NEIGHBOR nb, NODE node)
{//在nb节点群中增加一个相邻节点node
    NEIGHBOR b, pb;					//相邻节点变量 
    b = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));	//动态开辟一个相邻单元 
    b->next = NULL;
    Set(b->node, node, SetValue);					//本例中与strcpy(b->node, node);等价 
    if (nb == NULL)							//没有相邻节点的情况 
        nb = b;
    else									//有相邻节点的情况 
    {
        pb = nb;
        while (pb -> next) pb = pb -> next;
        pb -> next = b;
    }
    return nb;								//返回相邻节点 
}

GRAPH Form_Pa_Ch(NODE pa, NEIGHBOR nb) 
{//一个节点与其所有相邻节点
    GRAPH anynode;
    anynode = (GRAPH)malloc(sizeof(struct GRAPHNODE));//创建节点 
    Set(anynode->node.node, pa, SetValue);
    anynode->node.adjacents=nb;//相邻节点与节点成链 
    anynode->next=NULL;
    return anynode;								//返回节点
}

GRAPH AddAsubTree(GRAPH graph, GRAPH subgraph)	
{// 节点加入上一层节点
    GRAPH g = graph;			//临时(图),应该是链吧
    if(graph == NULL)		//图不存在 
        graph = subgraph;		//你懂得, 只有一个节点, 直接进
    else                    //图存在
    {
        while (g->next) g = g->next;
        g->next = subgraph;	//搞一个新的子链
    }
    return graph;			//返回图指针 
}

NEIGHBOR ClearAdjacents(NEIGHBOR nb)	
{//回收图节点空间 
    NEIGHBOR nb1 = nb;				//临时节点变量 
    while (nb)
    {
        nb1 = nb;
        nb = nb->next;
        free(nb1);					//回收单元 
    }
    return nb;						//返回NULL 
}

GRAPH ClearGraph(GRAPH graph)			//回收图节点相邻节点空间 
{
    GRAPH graph1 = graph;				//临时图
    while (graph)
    {
        graph1 = graph;
        graph = graph->next;
        free(graph1);				//回收单元 
    }
    return graph;					//返回NULL
}

void CreateStr(char *neighborset)	//字符数组转换为多个字符串 
{
    char *c = neighborset;				//临时字符串 
    while (*c)
    {
        if(*c == '/') *c = '\0';				//插入字符串结束标记 
        c++;
    }
    c++;
    *c = '\0';						//多一个结束标记 
}

NEIGHBOR CreateNeighbors(NEIGHBOR neighbors, char *neighborset)
{                                                   //若干个节点构成所有邻近节点
    char *p = neighborset;							//多个节点，分隔符'/' 
    NODE node;
    CreateStr(neighborset);							//变为多个字符串 
    while (*p)
    {//与strcpy(node, p);等价，读取节点 
        Set(node, p, SetValue);
        neighbors = AddANeighbor(neighbors, node);		//加入邻近关系中 
        p += strlen(node) + 1;
    }
    return neighbors;								//返回邻近节点链表 
}

GRAPH CreateGraph(GRAPH graph, char *filename)	//从文件创建树 
{
    GRAPH subgraph;
    NEIGHBOR neighbors;
    FILE *fp;
    char anynode[200], neighborset[5000];
    fp = fopen(filename, "r");
    while (!feof(fp))							//文件中是否还存在树的节点名称 
    {
        fscanf(fp, "%s", anynode);				//读入双亲节点 
        fscanf(fp, "%s", neighborset);
        neighbors = NULL;					//读入若干兄弟节点（子节点），分隔符'/' 
        neighbors = CreateNeighbors(neighbors, neighborset);		//构建双亲节点 
        subgraph = Form_Pa_Ch(anynode, neighbors);				//构建子树 
        graph = AddAsubTree(graph, subgraph);					//树中加入子树
    }
    fclose(fp);
    return graph; 
}

void main(int argc, char const *argv[])
{//建图
    GRAPH graph = NULL;                                       //链式存储结构图 
    char *filename="graph.txt";                              //图数据文件
    graph = CreateGraph(graph, filename);                      //创建链式存储结构图
    printf("\nGRAPH BUILD SUCCESS!\n");
    ClearGraph(graph);                                        //回收图空间
}
